1. Field of the Invention
The present invention generally relates to image processing. More specifically, the present invention relates to a lossless image compression algorithm.
2. Background Information
Typically, the performance that may be attained by an integrated circuit (IC) is directly linked to the number of transistors comprising the IC. Although IC technology varies greatly from one manufacturer to another, there is an upper bound as to the number of transistors any given IC may contain due to inherent limitations in IC manufacturing processes. Since, according to Moore""s Law, the number of transistors per square inch that can be processed onto an integrated circuit is predicted to double every 18 months, it can safely be assumed that integrated circuit performance will increase correspondingly.
Unfortunately, however, no matter how fast technological advances and associated performance increases are made, there are always manufacturers and/or system integrators that will be slow to implement such new technology. Even with xe2x80x9cstate of the artxe2x80x9d systems that incorporate the latest and greatest technology, consumers are nevertheless often left desiring greater performance. One catalyst behind consumer demand for increased IC (e.g., processor) performance can be associated with the computer graphics industry. Graphics designers, including video game designers for example, often stretch the bounds of technology by designing games, simulations, etc., that are extremely graphics-intensive. Some of these graphics designers push the performance envelope of existing hardware technology such that hardware designers are forced to play catch-up. Unfortunately, however, as soon as the capabilities of the hardware begin to meet the demands of the software and ultimately the consumer, a new software product will be released that once again requires additional hardware support, and so forth.
FIG. 1 is a block diagram illustrating a graphics sub-system within a basic personal computer. System 25 includes CPU 12, memory 14, data storage device 15, graphics engine 16, and frame buffer 18, all of which are coupled together through system bus 10. CPU 12 represents a general purpose processor known in the art to process instructions and data. Memory 14 represents one or more volatile or non-volatile memory storage devices to temporarily store instructions and data to be processed by CPU 12. Data storage device 15 represents a long term data storage device, such as a hard disk drive, to store instructions and data to be processed by CPU 12. Graphics engine 16 represents one or more special purpose integrated circuits to process graphics data received via system bus 10. Graphics engine 16 may represent any number of graphics controllers known in the art such as an AGP or PCI chipset. Although graphics engine 16 is shown coupled to system bus 10, graphics engine 16 may instead be coupled to a local or special purpose bus. Frame buffer 18 represents a data buffer equipped to temporarily store video frames and images processed by graphics engine 16. Frame buffer 18 is coupled to graphics engine 16 via back-end bus 17, which provided greater throughput between frame buffer 18 and graphics engine 16 than is available between graphics engine 16 and memory 14.
Video scenes are often broken down into multiple image frames which are further broken down into pixels. Typically, pixel representations for a currently-displayed frame and a next frame are stored in a buffer, such as frame buffer 18. Depending upon the image resolution, a full screen image may consume large amounts of memory. For example, in a 24-bit color plane (in which the greater the number of bits, the greater the number of colors that may be represented), 3 bytes of data are needed to accurately represent 1 pixel. Moreover, in a 1280xc3x971024 display resolution, the pixel representations would require over 3 Megabytes of storage space per frame! If both a current frame and a next frame are stored, over 6 megabytes of frame buffer storage would be required.
In order to provide realistic and even life-like images and video, software designers often utilize what are known as textures. Textures are used in conjunction with standard wire-frame images to prove an elevated level of realism to computer graphics. Generally, the more textures that are available for use, the more realistic an image can appear. Unfortunately, however, due to storage limitations of the frame buffer, textures are often stored in slower main memory (e.g., memory 14), rather than the faster frame buffer memory (e.g., frame buffer 18). Therefore, if pixel representations stored within the frame buffer could be minimized, additional textures could then be stored in the frame buffer.